﻿<HTML>

<HEAD>
  <META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=utf-8" />  
  <TITLE>HeO</TITLE>
  <LINK HREF="doc.css" REL=STYLESHEET>
</HEAD>


<BODY>


<!-- ============================================ -->

  <TABLE CLASS="header">
    <TBODY>
      <TR>
        <TD CLASS="head">HeO</TD>
        <TD CLASS="logo" ROWSPAN="2"><IMG CLASS="logosmall" SRC="../images/heo-logo.png"></IMG></TD>
      </TR>
      <TR>
        <TD CLASS="links"><A HREF="../index.html">[Previous]</A><A HREF="solvers.html">[Next]</A><A HREF="../index.html">[Home]</A></TD>
      </TR>
    </TBODY>
  </TABLE>
  

  <H2>Contents</H2>

  <UL>
    <LI><A HREF="#intro">Introduction</A></LI> 
    <LI><A HREF="#sysreq">System Requirements</A></LI> 
    <LI><A HREF="#install">Installation and Directory Structure</A></LI> 
    <LI><A HREF="#archit">Understanding HeO Acrchitecture</A></LI> 
  </UL>


<!-- ============================================ -->


  <A NAME="intro"></A>
  <H3>Introduction</H3>

  <P>
    <B>HeO</B> (<B>He</B>uristic <B>O</B>ptimization) is a cross-platform library that provides parallel metaheuristic algorithms for hard optimization problems. 
    The library is written in C++ using modern programming, metaprogramming and parallel computing techniques. 
    The main goal of the project is to provide the researchers with the state-of-the-art and easy-to-use software tool that can be applied to a wide range of optimization problems.
  </P> 

  <P>
    <B>Key features:</B>
  </P>  

   <UL>
    <LI>The source code is platform-independent and can be used on Windows and Linux systems without any alterations.</LI>
    <LI>x86 and x64 architectures are supported.</LI>
    <LI>All optimization methods are implemented as algorithmic skeletons (solvers) that can be applied to different optimization problems.</LI>
    <LI>Solvers are hybridization-ready.</LI>
    <LI>Each optimization method is implemented using two parallel programming techniques: OpenMP and MPI.</LI> 
    <LI>The MPI versions of the optimization methods use the original MPI wrapper compatible with MPICH and LAM libraries.</LI>
    <LI>Parallelism is fully transparent to the library users.</LI>
    <LI>The original reflection technology allows loading, saving, printing and passing instances in a uniform way.</LI>
    <LI>Wizards ease the process of creating user projects and running them on distributed and shared memory platforms.</LI>
  </UL>


<!-- ============================================ -->


  <A NAME="sysreq"></A>
  <H3>System Requirements</H3>

  <P>
    To build and run projects that use the HeO library you need to have installed: 
  </P>  

  <UL>
    <LI>MS VC++ (2005 or higher), GCC with OpenMP support (4.1.2 or higher) or Intel C++ Compiler (11.1 or higher) depending on your system.</LI>
    <LI>MPI-1 or MPI-2 library (e.g., MPICH or LAM).</LI>
    <LI>Platform SDK for Windows.</LI>
  </UL>

<!-- ============================================ -->


  <A NAME="install"></A>
  <H3>Installation and Directory Structure</H3>

  <P>
    To install the HeO library you have to perform the following steps:
  </P>  

  <OL>
    <LI>Download the appropriate source file.</LI>
    <LI>Unpack the downloaded source file into any desired folder.</LI>
    <LI>Change to the root folder of the library (<TT CLASS="folder">/heo</TT>).</LI>
  </OL>    
  
  <P>
    A brief (yet not complete) description of the HeO directory structure is given in the table below.
  </P>

    <TABLE>
      <TBODY>

        <TR>
          <TH COLSPAN="3">HeO Directory Structure</TH>
        </TR>

        <TR>
          <TH>Name</TH>
          <TH>Type</TH>
          <TH>Description</TH>
        </TR>

        <TR>
          <TD CLASS="l0">/heo</TD>
          <TD ALIGN="center">folder</TD>
          <TD>Root folder.</TD>
        </TR>


        <TR>
          <TD CLASS="l1">/contrib</TD>
          <TD ALIGN="center">folder</TD>
          <TD>Contributed files and libraries that are not considered part of the HeO library.</TD>
        </TR>

        <TR>
          <TD CLASS="l1">/doc</TD>
          <TD ALIGN="center">folder</TD>
          <TD>HeO documentation.</TD>
        </TR>

        <TR>
          <TD CLASS="l1">/logins</TD>
          <TD ALIGN="center">folder</TD>
          <TD>Files with logins and passwords (for MPI runs).</TD>
        </TR>



        <TR>
          <TD CLASS="l1">/problems</TD>
          <TD ALIGN="center">folder</TD>
          <TD>Problem instances.</TD>
        </TR>

        <TR>
          <TD CLASS="l2">/generic</TD>
          <TD ALIGN="center">folder</TD>
          <TD>Generic problem instances.</TD>
        </TR>

        <TR>
          <TD CLASS="l2">/maxsat</TD>
          <TD ALIGN="center">folder</TD>
          <TD>MAX-SAT problem instances.</TD>
        </TR>

        <TR>
          <TD CLASS="l2">/onemax</TD>
          <TD ALIGN="center">folder</TD>
          <TD>ONE-MAX problem instances.</TD>
        </TR>

        <TR>
          <TD CLASS="l2">...</TD>
          <TD ALIGN="center">folder</TD>
          <TD>Other problem instances.</TD>
        </TR>



        <TR>
          <TD CLASS="l1">/projects</TD>
          <TD ALIGN="center">folder</TD>
          <TD>Sample and user projects.</TD>
        </TR>

        <TR>
          <TD CLASS="l2">/generic</TD>
          <TD ALIGN="center">folder</TD>
          <TD>Sample generic projects.</TD>
        </TR>

        <TR>
          <TD CLASS="l2">/maxsat</TD>
          <TD ALIGN="center">folder</TD>
          <TD>Sample MAX-SAT projects.</TD>
        </TR>

        <TR>
          <TD CLASS="l2">/onemax</TD>
          <TD ALIGN="center">folder</TD>
          <TD>Sample ONE-MAX projects.</TD>
        </TR>

        <TR>
          <TD CLASS="l2">...</TD>
          <TD ALIGN="center">folder</TD>
          <TD>Other projects.</TD>
        </TR>



        <TR>
          <TD CLASS="l1">/solvers</TD>
          <TD ALIGN="center">folder</TD>
          <TD>Source files for algorithm-specific classes.</TD>
        </TR>

        <TR>
          <TD CLASS="l2">/ga</TD>
          <TD ALIGN="center">folder</TD>
          <TD>GA source files.</TD>
        </TR>

        <TR>
          <TD CLASS="l2">/sa</TD>
          <TD ALIGN="center">folder</TD>
          <TD>SA source files.</TD>
        </TR>


        <TR>
          <TD CLASS="l2">/hybrids</TD>
          <TD ALIGN="center">folder</TD>
          <TD>Source files for hybrid methods.</TD>
        </TR>



        <TR>
          <TD CLASS="l1">/src</TD>
          <TD ALIGN="center">folder</TD>
          <TD>Source files for auxillary classes and utilities.</TD>
        </TR>

        <TR>
          <TD CLASS="l1">/license.txt</TD>
          <TD ALIGN="center">file</TD>
          <TD>License agreement.</TD>
        </TR>

        <TR>
          <TD CLASS="l1">/readme.txt</TD>
          <TD ALIGN="center">file</TD>
          <TD>README file.</TD>
        </TR>

      </TBODY>
    </TABLE>
  
  <P>
  </P>

  
<!-- ============================================ -->


  <A NAME="archit"></A>
  <H3>Understanding HeO Architecture</H3>

  <P>
    The library is designed as a set of classes that can be divided into two large groups: 
  </P>

  <UL>
    <LI><B>Algorithm-specific classes</B>.</LI>
    <LI><B>Auxiliary classes</B>.</LI>
  </UL>

  <P>
    Algorithm-specific classes abstract the features specific to optimization methods. 
    Their source code is stored in the <TT CLASS="folder">/heo/solvers</TT> folder.
    Auxiliary classes perform different subsidiary functions.
    Their source code is stored in the <TT CLASS="folder">/heo/src</TT> folder.
  </P>

  <P>
    At present two optimizations methods are implemented: genetic algorithm (GA) and simulated annealing (SA).
    The actual number of the available methods may be increased by their hybridization.
  </P>

  <P>
    The core of the algorithm-specific classes are the so-called <B>solvers</B>. 
    Each solver is a class template that implements the particular optimization method using the particular parallel programming technique.
    This means that there are four solvers in the library (two for each optimization method).
  </P>

  <P>
    The name of each solver consists of the name of the optimization method and the abbreviation of the parallel programming technique with underscore between words.
    For example, <TT>GA_OMP</TT> means the solver that implements the OpenMP version of the genetic algorithm.
  </P>

  <P>
    The source code for the solvers that implement the same optimization method is contained in the folder <TT CLASS="folder">/heo/solvers/&lt;method&nbsp;name&gt;</TT> in the following files:
  </P>

  <UL>
    <LI><TT>&lt;method&nbsp;name&gt;_common.h &mdash;</TT> part of the source code common to both solvers.</LI>
    <LI><TT>&lt;method&nbsp;name&gt;_mpi.h &mdash;</TT> source code for the MPI solver.</LI>
    <LI><TT>&lt;method&nbsp;name&gt;_omp.h &mdash;</TT> source code for the OpenMP solver.</LI>
  </UL>

  <P>
     For example, the source code for both SA solvers is stored in the folder <TT CLASS="folder">/heo/solvers/sa</TT> in the files <TT>sa_common.h</TT>, <TT>sa_mpi.h</TT> and <TT>sa_omp.h</TT>.
  </P>

  <P>
     Solvers of the HeO library are designed as <B>algorithmic skeletons</B>. 
     This means that each solver:
  </P>

  <UL>
    <LI>Abstracts only algorithm-specific features regardless of any optimization problem.</LI>
    <LI>Hides all aspects regarding parallelization.</LI>
  </UL>

  <P>
     This approach allows to apply each solver to a wide range of optimization problems and makes parallelism transparent to the library users.   
  </P>

  <P>
    All solvers are declared as class templates. 
    Solvers for one and the same optimization method are derived from one and the same parent class template.
    For example, <TT>SA_MPI</TT> and <TT>SA_OMP</TT> class templates are derived from the parent class template <TT>SA</TT>.  
    Below is the example of the <TT>SA_MPI</TT> class template declaration from the <TT>sa_mpi.h</TT>:
  </P>

  <DIV CLASS="code">
    template&lt;class Traits&gt;<BR>
    class SA_MPI:<BR>
    &nbsp;&nbsp;&nbsp;&nbsp;public SA&lt;Traits&gt;<BR>
    {<BR>
    &nbsp;...<BR>
    }<BR>
  </DIV>


  <P>
    The template parameter <TT>Traits</TT> in this declaration is a special algorithm-specific class that provides the solver with all necessary data which allow to control its behavior. 
    Note, that this class itself <I>does not store any data</I>. 
    This class may be called as "syntactic sugar" because its only purpose is to simplify the source code. 
    For SA the corresponding class is called <TT>SA_Traits</TT>. 
    It is implemented in the file <TT>sa_common.h</TT> and its declaration is as follows:
  </P>


  <DIV CLASS="code">
    template&lt;class Environment&gt;<BR>
    struct SA_Traits<BR>
    {<BR>
    &nbsp;...<BR>
    }<BR>
  </DIV>

  <P>
    Here the template parameter <TT>Environment</TT> means an auxiliary class that contains all necessary information about problem-specific classes and run parameters (like number of independent runs, debug level, etc). 
    This template class has the following parameters: <TT>Problem</TT>, <TT>Solution</TT> and <TT>Config</TT>. 
    These parameters correspond to <B>problem-specific</B> classes implemented by the user.
    The first two classes abstract the features of the problem and its admissible solutions respectively. 
    In order to have the ability to interact with the solver these classes must have necessary methods specific to optimization algorithm (e.g., the method that makes a move for SA).
    The third parameter is the problem-specific configuration class.
    Note, that all user source files and projects are stored in the <TT CLASS="folder">/heo/projects</TT> folder.
  </P>


  <P>
    To apply the desired solver to the particular problem the user usually has to perform a number of standard operations: read command line parameters, configuration file and problem instance file (if any), initialize and run solver, print the results, etc. 
    There are two auxiliary classes (so called <B>runners</B>) that perform this routine: <TT>Run_MPI</TT> and <TT>Run_OMP</TT>.
    Below is the example of the <TT>Run_MPI</TT> class template declaration from the <TT>run_mpi.h</TT>:
  </P>

  <DIV CLASS="code">
    template&lt;class Solver&gt;<BR>
    class Run_MPI<BR>
    {<BR>
    &nbsp;...<BR>
    }</BR>
  </DIV>


  <P>
    To automatically run the desired MPI or OpenMP solver the user has to substitute it for <TT>Solver</TT> template parameter in the <TT>Run_MPI</TT> or <TT>Run_OMP</TT> class templates. 
  </P>

  <P>
    The last class to be mentioned here is the <TT>Solution_Pool</TT> class. 
    It is used for hybridization purposes and has one template parameter <TT>Solution</TT> which correponds to the problem-specific class implemented by the user. 
  </P>

  <P>
    Algorithm-specific (for SA optimization method only) and auxiliary class templates along with their parameters are shown on the UML diagram below in red and yellow respectively.
  </P>

  <IMG SRC="../images/uml1.png" WIDTH="800px"></IMG>

  <P>
    Suppose that the user has implemented the problem-specific classes for the well-known MAX-SAT problem and now he or she wants to use <TT>SA_MPI</TT> solver to solve it.
    Then he or she needs to bind the template parameters of <TT>Environment</TT>, <TT>SA_Traits</TT>, <TT>SA_MPI</TT> and <TT>Run_MPI</TT> class templates to their actual values (the template parameter of the <TT>Solution_Pool</TT> is bound automatically).
    The next UML diagram demonstrates the relationships between the classes for this case (problem-specific classes are shown in green).
  </P>

  <IMG SRC="../images/uml2.png" WIDTH="800px"></IMG>

   <P>
  </P>

 
  <H2>&nbsp;</H2>

  <A HREF="../index.html">[Previous]</A><A HREF="solvers.html">[Next]</A><A HREF="../index.html">[Home]</A>


<!-- ============================================ -->


</BODY>

</HTML>


